package org.cllib.ds;

import java.util.Comparator;

public class Heap {
	protected Comparator c;
	public static int INITIAL_CAPACITY = 8;
	public static int CAPACITY_STEP = 8;
	
	protected Object[] elements;
	protected int numElements;
	protected int capacity;
	
	public Heap(Comparator c){
		this.c = c;
	}
	
	public void insert(Object o){
		if(numElements >= capacity){
			Object[] temp = new Object[numElements + CAPACITY_STEP];
			if(elements != null){
				System.arraycopy(elements, 0, temp, 0, numElements);				
			}
			capacity += CAPACITY_STEP;
			elements = temp;
			temp = null;
		}
		
		int newIndex = numElements;
		while(hasParent(newIndex)){
			if(c.compare(o, getParent(newIndex)) < 0){
				elements[newIndex] = getParent(newIndex);
				newIndex = parent(newIndex);
			}else{
				break;
			}
		}
		elements[newIndex] = o;
		numElements ++;
	}
	
	public boolean contains(Object o){
		return indexOf(o) != -1;
	}
	
	int indexOf(Object o){
		int index = 0;
		while(index < numElements){
			if(o.equals(elements[index])){
				return index;
			}else if(c.compare(o, elements) < 0){
				index = left(index);
			}else if(c.compare(o, elements) > 0){
				index = right(index);
			}else {
				throw new IllegalStateException("Inconstancy found between equals and compare");
			}
		}
		
		return -1;
	}
	
	public void remove(Object o){
		int index = indexOf(o);
		
		if(index < 0){
			return;
		}

		Object last = elements[numElements - 1];
		
		while(hasLeft(index)){
			Object left = getLeft(index);
			int min = left(index);
			if(hasRight(index)){
				Object right = getRight(index);
				if(c.compare(right, left) < 0){
					min = right(index);
				}
			}
			
			Object minObject = elements[min];
			if(c.compare(last, minObject) < 0){
				break;
			}else{
				elements[index] = minObject; 
				index = min;
			}
		}
		
		elements[index] = last;
		elements[numElements - 1] = null;
		
		numElements --;
	}
	
	public Object extract(){
		Object o = peek();
		
		remove(o);
		
		return o;
	}
	
	public int size(){
		return numElements;
	}
	
	public boolean isEmpty(){
		return numElements <= 0;
	}
	
	public Object peek(){
		if(numElements <= 0){
			return null;
		}else{
			return elements[0];
		}
	}
	
	int parent(int index){
		return (index - 1) / 2;
	}
	
	Object getParent(int index){
		return elements[parent(index)];
	}
	
	boolean hasParent(int index){
		return index > 0 && parent(index) >= 0;
	}
	
	int left(int index){
		return 2 * index + 1;
	}
	
	boolean hasLeft(int index){
		return left(index) < numElements;
	}
	
	int right(int index){
		return 2 * index + 2;
	}
	
	boolean hasRight(int index){
		return right(index) < numElements;
	}
	
	Object getLeft(int index){
		return elements[left(index)];
	}
	
	Object getRight(int index){
		return elements[right(index)];
	}
}
